The present invention relates to a data management method and apparatus for use when entry data is registered in an entry table.
FIG. 7 is an example of a conceptual diagram explaining about a conventional data management method.
A high-speed semiconductor memory such as SRAM, for example, is used as an entry table 30 and a predetermined number of entry data 32 are registerable in the entry table 30. Usually, the number of entry data 32 registerable in the entry table 30 is limited and entry data 32 of 1K (=1,024) are assumed to be registerable in this case. The entry data 32 registered in the entry table 30 can be used by reading out the data as occasion demands.
When a request for the registration of a new entry data 34 is made to the entry table 30, the new entry data 34 is basically registered at a free entry address in the entry table 30. In case no free entry address is found, however, an unwanted entry data is detected and deleted out of the entry data 32 of 1K already registered, so that the new entry data 34 is registered at the entry address thus deleted.
In this case, the unwanted entry data is set properly by a user of a data management apparatus as necessary by setting at least one specific condition for the management of the entry data 32 registered in the entry table 30 such that the unwanted entry data is determined by an order of registration or from the fact that it remains less frequently used or unused for a predetermined time, for example.
A description will subsequently be given of an example of the prior art data management method in order to understand problems pertaining thereto. In order to simplify an explanation, it will be assumed that the entry data 32 registered in the entry table 30 are arranged in order of size and when a request for the registration of the new entry data 34 is made, what has the lowest value, for example, among the entry data 32 of 1K registered in the entry table 30 is to be treated as what is unwanted and deleted.
In this case, it becomes necessary to detect an entry address at which the new entry data 34 should be registered and to rearrange the entry data 32 accordingly. By doing a binary search eleven times through the entry data of 1K, for example, the entry address at which the new entry data 34 should be registered can be calculated. The time required for calculating the entry address is 1.1 xcexcs on the assumption that the time required for doing one binary search is 100 ns.
For rearranging the entry data 32 in order of size, it is necessary that not only reading the entry data 32 whose respective values are smaller than that of the new entry data 34 sequentially but also writing them at destination entry addresses sequentially as shown in FIG. 7. Assuming that 50 ns is necessary for moving one entry data 32, the time required to move all of the entry data 32 amounts to 50 xcexcs (1Kxc3x9750 ns) when things come to the worst in a case where the new entry data 34 has the largest value (see FIG. 7).
In the prior art data management method and apparatus so designed as to make a rearrangement of entry data 32, a relatively long time is needed until the new entry data 34 is registered despite the use of a high-speed semiconductor memory such as SRAM and an objective retrieval operation is unperformable during this time. Although the number of entry data 32 registerable in the entry table 30 has been set at 1K as described above, the time required for the management of entry data increases as the number of entry data increases because there may be a case where more entry data are registered.
Consequently, there is a problem that the prior art data management method and apparatus is unfit for use which requires simultaneous data update and high speed retrieval operation, for example, Internet network addresses.
An object of the present invention is to solve the above mentioned prior art problem, and to provide a data management method and apparatus capable of managing entry data at high speed through a simple procedure and with a simple configuration.
In order to accomplish the object above, the present invention provides a data management method for use when a demand for the registration of a new entry data is made in order to register the new entry data by deleting a specific entry data out of a plurality of n-bit (n=a positive integer) entry data registered beforehand, comprises the steps of:
registering the plurality of entry data having n-bit length;
performing match retrieval repeatedly by masking a (nxe2x88x92m(i)) bit (m(i)=a positive integer satisfying nxe2x89xa7m(i)) from the least significant bit side, whereby detecting the value of an m(i) bit from the side of the most significant bit matching the specific entry data;
performing match retrieval by shifting a bit to be masked next by an m(i+1) bit (m(i+1) a positive integer satisfying (nxe2x88x92m(i))xe2x89xa7m(i+1)) toward the low order side and detecting a corresponding value of m(i+1) bit until no bit to be masked exists so as to detect the value of an n bit matching the specific entry data; and
obtaining an entry address at which the specific entry data matching the value of the n bit thus detected has been registered, so that the new entry data is registered at the entry address.
It is preferred that match retrieval is performed again by the use of the value of the n bit matching the specific entry data thus detected so as to detect the entry address of the specific entry data.
Preferably, the specific entry data has the lowest value, the highest value or a value nearest a predetermined value. A condition for the detection of the specific entry data is preferably one of entry data registration order, frequency in use and elapsed time after the registration.
The m(i+1) bit is preferably one bit or two bits.
Also the present invention provides a data management apparatus comprises:
an associative memory having at least one mask register for masking the predetermined bit of retrieval data, and at least a memory array in which a plurality of n-bit (n=a positive integer) entry data are registered, the memory array being used for performing match retrieval of the retrieval data masked by the mask register and the plurality of entry data; and
a control circuit for controlling the associative memory in such a way as performing match retrieval by masking an (nxe2x88x92m(i)) bit (m(i)=a positive integer satisfying nxe2x89xa7m(i)) from the least significant bit side of the retrieval data by means of the mask register, detecting the value of the m(i) bit from the side of the most significant bit matching the specific entry data according to a result of match retrieval, and performing match retrieval repeatedly by shifting a bit to be masked next by an m(i+1) bit (m(i+1)=a positive integer satisfying (nxe2x88x92m(i))xe2x89xa7m(i+1)) toward the low order side and detecting a corresponding value of m(i+1) bit until no bit to be masked exists so as to detect not only the value of n bit matching the specific entry data but also an entry address at which the specific entry data has been registered.
It is preferred that the associative memory feeds to the control circuit a hit detection signal for indicating that at least one entry data matching the retrieval data has been registered in the memory array.
The control circuit is preferably formed of only hardware.
The associative memory and the control circuit are preferably formed of a semiconductor chip.
The control circuit is preferably formed of only software or a combination of software and hardware.
The m(i+1) bit is preferably one bit or two bits.
The mask register preferably has a function of shifting a bit to be masked by the m(i+1) bit each time toward the low order side under the control of the control circuit.
It is preferred that the associative memory further includes an input data register for holding the retrieval data and wherein the input data register is capable of setting and resetting the value of the retrieval data on a 1-bit basis under the control of the control circuit.
In the data management method and apparatus according to the present invention, a specific entry data is detected out of the entry data registered in the associative memory so that a new entry data can be registered at the entry address of the entry data thus detected, in other words, the use of the associative memory makes it unnecessary to rearrange the entry data, thus it is easy to process data, and the rearrangement of the entry data can be performed at an extremely high speed, irrespective of the number of registered entry data.